package com.leetcode.题库;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-02-27 20:28
 */
public class 题库_0022_括号生成 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    List<String> parenthesis = solution.generateParenthesis(5);
    System.out.println(parenthesis);
  }

  static
  class Solution {
    public List<String> generateParenthesis(int n) {
      List<String> answers = new ArrayList<>();
      backtrack(n, 1, 0, "(", answers);
      return answers;
    }

    private void backtrack(int n, int open, int close, String cur, List<String> answers) {
      if (cur.length() == n * 2) {
        answers.add(cur);
        return;
      }

      // 放左括号
      if (open < n) {
        backtrack(n, open + 1, close, cur + '(', answers);
      }

      // 放右括号
      if (close < open) {
        backtrack(n, open, close + 1, cur + ')', answers);
      }

    }


    private Set<String> recursivelyGenerateParenthesis(int n) {
      if (n == 0) {
        return new HashSet<>(Collections.singletonList(""));
      }
      Set<String> result = new HashSet<>();
      for (int i = 0; i < n; ++i) {
        Set<String> lefts = recursivelyGenerateParenthesis(i);
        Set<String> rights = recursivelyGenerateParenthesis(n - i - 1);
        for (String leftStr : lefts) {
          for (String rightStr : rights) {
            result.add("(" + leftStr + ")" + rightStr);
          }
        }
      }
      return result;
    }
  }

}
